class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int n = nums.size(),sum = 0;
            for(int i = 0;i < n;i++){
                sum += nums[i];
            }
            if(sum%2 == 1) return false; 
            vector<bool> dp(sum/ 2 + 1,false);
            dp[0] = true;
            for(int i : nums){
                for(int j = sum /2;j >= i ;j--){
                    dp[j] = dp[j - i] || dp[j];
                }
            }
            return dp[sum / 2];
        }
    };